package org.java;

import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

public class Tree {
	private List<Object[]> deepList = new ArrayList<Object[]>();// 假设Object[]长度为2，object[0]表示id，object[1]表示pid
	private Set<List> set = new HashSet<List>();

	public void toDeepTree(Map<Integer, Object[]> map, Object pid) {
		// System.out.println(list.size());
		// System.out.println(deepList==null?0:deepList.size()+" "+(list==null?0:list.size()));

		int index = 0;
		int index2 = 0;
		if (map == null || map.size() == 0)// 如果源list为空（相当于队列为空时）返回
			return;
		Object obj[];

		Iterator it = map.entrySet().iterator();
		try {
			if (deepList == null || deepList.size() == 0)// 如果目标list为空，则放一个根元素进去（这里假设根元素是唯一的）
			{
				while (it.hasNext()) {
					Map.Entry key = (Entry) it.next();
					obj = (Object[]) key.getValue();
					if (obj[1] == null)// 如果pid为null，说明这个是根元素
					{
						deepList.add(obj);

						it.remove();
						map.remove(obj[0]);// 把该元素移出
						// it=list.iterator();
						toDeepTree(map, obj[0]);// 重新来一次
					}
					index++;// 对应源list的索引++
				}
				return;// 如果没有pid为null的object[]，则返回
			} else {
				// Object objTemp[]=(Object[])deepList.get(deepList.size()-1);
				while (it.hasNext()) {
					Map.Entry key = (Entry) it.next();
					obj = (Object[]) key.getValue();

					if (obj[1].equals(pid))// 如果该obj[]的pid等于它上面那个元素的id，则在目标list中加入该obj[]
					{
						deepList.add(obj);

						it.remove();
						map.remove(obj[0]);// 移出
						index2 = -1;// 为避免数组越界，将index2置为-1，然后下面index2++的时候又置为0。
						// it=list.iterator();//因为list已经改变，所以重新跌代
						toDeepTree(map, obj[0]);// 再来一次
					}
					index2++;
				}

				if (map == null || map.size() == 0) {
					return;
				}
			}
		} catch (ConcurrentModificationException e) {
			// 以最后以为向上添加
			for (int i = deepList.size() - 1; i > 0; i--) {
				Object[] obj1 = (Object[]) deepList.get(i);
				toDeepTree(map, obj1[1]);// 再来一次
			}
		}

		// System.out.println(index);
	}

	public List getList() {
		return deepList;
	}

	public static void main(String[] s) {
		Object obj1[] = { 0, null };
		Object obj2[] = { 1, 0 };
		Object obj3[] = { 3, 0 };
		Object obj4[] = { 4, 1 };
		Object obj5[] = { 7, 1 };
		Object obj6[] = { 8, 1 };
		Object obj7[] = { 2, 3 };
		Object obj8[] = { 9, 3 };
		Object obj9[] = { 10, 3 };
		Object obj10[] = { 15, 2 };
		Object obj11[] = { 6, 2 };
		Object obj12[] = { 5, 7 };

		Map<Integer, Object[]> map = new HashMap<Integer, Object[]>();
		map.put(0, obj1);
		map.put(1, obj2);
		map.put(3, obj3);
		map.put(4, obj4);
		map.put(7, obj5);
		map.put(8, obj6);
		map.put(2, obj7);
		map.put(9, obj8);
		map.put(10, obj9);
		map.put(15, obj10);
		map.put(6, obj11);
		map.put(5, obj12);

		Tree tree = new Tree();
		List remList = new ArrayList();
		tree.toDeepTree(map, null);
		List dlist = tree.getList();
		if (dlist == null)
			System.out.println("null");
		Iterator it = dlist.iterator();
		while (it.hasNext()) {
			Object o[] = (Object[]) it.next();
			System.out.println(o[0] + " " + o[1]);
		}

	}
}